/*-------------------------------------------------------------------------
 *
 * gist.c
 *	  postgres GiST 索引访问方法的接口例程。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/access/gist/gist.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/gist_private.h"
#include "access/gistscan.h"
#include "access/xloginsert.h"
#include "catalog/pg_collation.h"
#include "commands/vacuum.h"
#include "miscadmin.h"
#include "nodes/execnodes.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
#include "utils/builtins.h"
#include "utils/index_selfuncs.h"
#include "utils/memutils.h"
#include "utils/rel.h"

/* 非导出函数原型 */
static void fc_gistfixsplit(GISTInsertState *fc_state, GISTSTATE *fc_giststate);
static bool fc_gistinserttuple(GISTInsertState *fc_state, GISTInsertStack *fc_stack,
							GISTSTATE *fc_giststate, IndexTuple fc_tuple, OffsetNumber fc_oldoffnum);
static bool fc_gistinserttuples(GISTInsertState *fc_state, GISTInsertStack *fc_stack,
							 GISTSTATE *fc_giststate,
							 IndexTuple *fc_tuples, int fc_ntup, OffsetNumber fc_oldoffnum,
							 Buffer fc_leftchild, Buffer fc_rightchild,
							 bool fc_unlockbuf, bool fc_unlockleftchild);
static void fc_gistfinishsplit(GISTInsertState *fc_state, GISTInsertStack *fc_stack,
							GISTSTATE *fc_giststate, List *fc_splitinfo, bool fc_unlockbuf);
static void fc_gistprunepage(Relation fc_rel, Page fc_page, Buffer fc_buffer,
						  Relation fc_heapRel);


#define ROTATEDIST(d) do { \
	SplitedPageLayout *fc_tmp=(SplitedPageLayout*)palloc0(sizeof(SplitedPageLayout)); \
	fc_tmp->block.blkno = InvalidBlockNumber;	\
	fc_tmp->buffer = InvalidBuffer;	\
	fc_tmp->next = (d); \
	(d)=fc_tmp; \
} while(0)


/*
 * GiST 处理程序函数：返回包含访问方法参数和回调的 IndexAmRoutine。
 */
Datum gisthandler(PG_FUNCTION_ARGS)
{
	IndexAmRoutine *fc_amroutine = makeNode(IndexAmRoutine);

	fc_amroutine->amstrategies = 0;
	fc_amroutine->amsupport = GISTNProcs;
	fc_amroutine->amoptsprocnum = GIST_OPTIONS_PROC;
	fc_amroutine->amcanorder = false;
	fc_amroutine->amcanorderbyop = true;
	fc_amroutine->amcanbackward = false;
	fc_amroutine->amcanunique = false;
	fc_amroutine->amcanmulticol = true;
	fc_amroutine->amoptionalkey = true;
	fc_amroutine->amsearcharray = false;
	fc_amroutine->amsearchnulls = true;
	fc_amroutine->amstorage = true;
	fc_amroutine->amclusterable = true;
	fc_amroutine->ampredlocks = true;
	fc_amroutine->amcanparallel = false;
	fc_amroutine->amcaninclude = true;
	fc_amroutine->amusemaintenanceworkmem = false;
	fc_amroutine->amparallelvacuumoptions =
		VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP;
	fc_amroutine->amkeytype = InvalidOid;

	fc_amroutine->ambuild = gistbuild;
	fc_amroutine->ambuildempty = gistbuildempty;
	fc_amroutine->aminsert = gistinsert;
	fc_amroutine->ambulkdelete = gistbulkdelete;
	fc_amroutine->amvacuumcleanup = gistvacuumcleanup;
	fc_amroutine->amcanreturn = gistcanreturn;
	fc_amroutine->amcostestimate = gistcostestimate;
	fc_amroutine->amoptions = gistoptions;
	fc_amroutine->amproperty = gistproperty;
	fc_amroutine->ambuildphasename = NULL;
	fc_amroutine->amvalidate = gistvalidate;
	fc_amroutine->amadjustmembers = gistadjustmembers;
	fc_amroutine->ambeginscan = gistbeginscan;
	fc_amroutine->amrescan = gistrescan;
	fc_amroutine->amgettuple = gistgettuple;
	fc_amroutine->amgetbitmap = gistgetbitmap;
	fc_amroutine->amendscan = gistendscan;
	fc_amroutine->ammarkpos = NULL;
	fc_amroutine->amrestrpos = NULL;
	fc_amroutine->amestimateparallelscan = NULL;
	fc_amroutine->aminitparallelscan = NULL;
	fc_amroutine->amparallelrescan = NULL;

	PG_RETURN_POINTER(fc_amroutine);
}

/*
 * 为 GiST 创建并返回一个临时内存上下文。我们
 * _始终_ 在一个临时内存上下文中调用用户提供的方法，
 * 这样这些函数中的内存泄漏就不会导致问题。此外，我们在
 * GiST 代码中使用一些额外的临时上下文，以避免需要进行一些笨拙的手动
 * 内存管理。
 */
MemoryContext createTempGistContext(void)
{
	return AllocSetContextCreate(CurrentMemoryContext,
								 "GiST temporary context",
								 ALLOCSET_DEFAULT_SIZES);
}

/*
 *	gistbuildempty() -- 在初始化叉中构建一个空的 gist 索引
 */
void gistbuildempty(Relation fc_index)
{
	Buffer		fc_buffer;

	/* 初始化根页面 */
	fc_buffer = ReadBufferExtended(fc_index, INIT_FORKNUM, P_NEW, RBM_NORMAL, NULL);
	LockBuffer(fc_buffer, BUFFER_LOCK_EXCLUSIVE);

	/* 初始化和 xlog 缓冲区 */
	START_CRIT_SECTION();
	GISTInitBuffer(fc_buffer, F_LEAF);
	MarkBufferDirty(fc_buffer);
	log_newpage_buffer(fc_buffer, true);
	END_CRIT_SECTION();

	/* 解锁并释放缓冲区 */
	UnlockReleaseBuffer(fc_buffer);
}

/*
 *	gistinsert -- GiST 元组插入的包装器。
 *
 *	  这是 GiSTs 中元组插入的公共接口例程。
 *	  它不执行任何工作；只是锁定关系并传递责任。
 */
bool gistinsert(Relation fc_r, Datum *fc_values, bool *fc_isnull,
		   ItemPointer fc_ht_ctid, Relation fc_heapRel,
		   IndexUniqueCheck fc_checkUnique,
		   bool fc_indexUnchanged,
		   IndexInfo *fc_indexInfo)
{
	GISTSTATE  *fc_giststate = (GISTSTATE *) fc_indexInfo->ii_AmCache;
	IndexTuple	fc_itup;
	MemoryContext fc_oldCxt;

	/* 如果这是该语句中的第一次调用，则初始化 GISTSTATE 缓存 */
	if (fc_giststate == NULL)
	{
		fc_oldCxt = MemoryContextSwitchTo(fc_indexInfo->ii_Context);
		fc_giststate = initGISTstate(fc_r);
		fc_giststate->tempCxt = createTempGistContext();
		fc_indexInfo->ii_AmCache = (void *) fc_giststate;
		MemoryContextSwitchTo(fc_oldCxt);
	}

	fc_oldCxt = MemoryContextSwitchTo(fc_giststate->tempCxt);

	fc_itup = gistFormTuple(fc_giststate, fc_r,
						 fc_values, fc_isnull, true /* 大小当前是虚假的 */ );
	fc_itup->t_tid = *fc_ht_ctid;

	gistdoinsert(fc_r, fc_itup, 0, fc_giststate, fc_heapRel, false);

	/* 清理 */
	MemoryContextSwitchTo(fc_oldCxt);
	MemoryContextReset(fc_giststate->tempCxt);

	return false;
}


/*
 * 将元组从 'itup' 放置到 'buffer' 中。如果 'oldoffnum' 有效，元组
 * 在该偏移量上会与插入的新元组原子地移除。
 * 这用于用一个新元组替换旧元组。
 *
 * 如果 'leftchildbuf' 有效，我们正在插入页面
 * 右侧 'leftchildbuf' 的下行链接，或更新 'leftchildbuf' 的下行链接。
 * 'leftchildbuf' 上的 F_FOLLOW_RIGHT 标志被清除，NSN 被设置。
 *
 * 如果 'markfollowright' 为真且页面被拆分，左子节点被
 * 标记为 F_FOLLOW_RIGHT 标志。这是正常情况。然而，在缓冲区
 * 索引构建期间，没有并发访问，页面拆分以一种稍微简单的方式进行，并传递假值。
 *
 * 如果页面上没有足够的空间，它将被拆分。所有拆分
 * 的页面都保持固定和锁定，并在 *splitinfo 中返回，调用者
 * 负责为它们插入下行链接。然而，如果 'buffer' 是根页面并且
 * 需要拆分，gistplacetopage() 将作为一个原子操作执行拆分，*splitinfo 被设置为 NIL。
 * 在这种情况下，我们继续保持根页面锁定，而子页面被释放；注意，新元组
 * 不在根页面上，而是在新的子页面之一中。
 *
 * 如果 'newblkno' 不是 NULL，返回插入第一个
 * 新的/更新的元组的页面的块号。通常是给定页面，但如果页面被拆分，
 * 可能是其右兄弟。
 *
 * 如果页面被拆分，返回 'true'，否则返回 'false'。
 */
bool gistplacetopage(Relation fc_rel, Size fc_freespace, GISTSTATE *fc_giststate,
				Buffer fc_buffer,
				IndexTuple *fc_itup, int fc_ntup, OffsetNumber fc_oldoffnum,
				BlockNumber *fc_newblkno,
				Buffer fc_leftchildbuf,
				List **fc_splitinfo,
				bool fc_markfollowright,
				Relation fc_heapRel,
				bool fc_is_build)
{
	BlockNumber fc_blkno = BufferGetBlockNumber(fc_buffer);
	Page		fc_page = BufferGetPage(fc_buffer);
	bool		fc_is_leaf = (GistPageIsLeaf(fc_page)) ? true : false;
	XLogRecPtr	fc_recptr;
	int			fc_i;
	bool		fc_is_split;

	/*
	 * 拒绝修改一个未完全分割的页面。这不应该发生，因为我们在遍历树时会完成任何未完成的分割。然而，远程可能会有另一个并发插入者分割了父页面，并在完成分割之前出错。在这种情况下，我们只会抛出一个错误，并将我们正在进行的任何分割也留作未完成。下一个到来的插入将清理这个混乱。
	 */
	if (GistFollowRight(fc_page))
		elog(ERROR, "concurrent GiST page split was incomplete");

	/* 永远不要尝试向已删除的页面插入 */
	Assert(!GistPageIsDeleted(fc_page));

	*fc_splitinfo = NIL;

	/*
	 * 如果是更新，删除旧键：该节点的键已被修改，可能是因为发生了子分割，或者因为我们需要调整键以便在子节点中插入。因此，删除该节点键的旧版本。
	 *
	 * 对于WAL重放，在非分割情况下，我们通过设置一个包含一个元素的待删除数组来处理；在分割情况下，由于传递给gistSplit的元组向量不会包含该元组，因此隐含地处理。
	 */
	fc_is_split = gistnospace(fc_page, fc_itup, fc_ntup, fc_oldoffnum, fc_freespace);

	/*
	 * 如果叶子页面已满，首先尝试删除死元组。然后再次检查。
	 */
	if (fc_is_split && GistPageIsLeaf(fc_page) && GistPageHasGarbage(fc_page))
	{
		fc_gistprunepage(fc_rel, fc_page, fc_buffer, fc_heapRel);
		fc_is_split = gistnospace(fc_page, fc_itup, fc_ntup, fc_oldoffnum, fc_freespace);
	}

	if (fc_is_split)
	{
		/* 没有插入空间 */
		IndexTuple *fc_itvec;
		int			fc_tlen;
		SplitedPageLayout *fc_dist = NULL,
				   *fc_ptr;
		BlockNumber fc_oldrlink = InvalidBlockNumber;
		GistNSN		fc_oldnsn = 0;
		SplitedPageLayout fc_rootpg;
		bool		fc_is_rootsplit;
		int			fc_npage;

		fc_is_rootsplit = (fc_blkno == GIST_ROOT_BLKNO);

		/*
		 * 形成索引元组向量以进行分割。如果我们在替换旧元组，则从向量中删除旧版本。
		 */
		fc_itvec = gistextractpage(fc_page, &fc_tlen);
		if (OffsetNumberIsValid(fc_oldoffnum))
		{
			/* 在内部页面上我们应该删除旧元组 */
			int			fc_pos = fc_oldoffnum - FirstOffsetNumber;

			fc_tlen--;
			if (fc_pos != fc_tlen)
				memmove(fc_itvec + fc_pos, fc_itvec + fc_pos + 1, sizeof(IndexTuple) * (fc_tlen - fc_pos));
		}
		fc_itvec = gistjoinvector(fc_itvec, &fc_tlen, fc_itup, fc_ntup);
		fc_dist = gistSplit(fc_rel, fc_page, fc_itvec, fc_tlen, fc_giststate);

		/*
		 * 检查分割是否产生了过多的页面。
		 */
		fc_npage = 0;
		for (fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
			fc_npage++;
		/* 在根分割中，我们将在下面的列表中添加一页 */
		if (fc_is_rootsplit)
			fc_npage++;
		if (fc_npage > GIST_MAX_SPLIT_PAGES)
			elog(ERROR, "GiST page split into too many halves (%d, maximum %d)",
				 fc_npage, GIST_MAX_SPLIT_PAGES);

		/*
		 * 设置要处理的页面。为所有页面分配新缓冲区，除了最左侧的页面。原始页面成为新的最左侧页面，并用新内容替换。
		 *
		 * 对于根分割，分配所有子页面的新缓冲区，原始页面被新根页面覆盖，其中包含对新子页面的向下链接。
		 */
		fc_ptr = fc_dist;
		if (!fc_is_rootsplit)
		{
			/* 保存旧的右链接和NSN */
			fc_oldrlink = GistPageGetOpaque(fc_page)->rightlink;
			fc_oldnsn = GistPageGetNSN(fc_page);

			fc_dist->buffer = fc_buffer;
			fc_dist->block.blkno = BufferGetBlockNumber(fc_buffer);
			fc_dist->page = PageGetTempPageCopySpecial(BufferGetPage(fc_buffer));

			/* 清除除F_LEAF之外的所有标志 */
			GistPageGetOpaque(fc_dist->page)->flags = (fc_is_leaf) ? F_LEAF : 0;

			fc_ptr = fc_ptr->next;
		}
		for (; fc_ptr; fc_ptr = fc_ptr->next)
		{
			/* 分配新页面 */
			fc_ptr->buffer = gistNewBuffer(fc_rel);
			GISTInitBuffer(fc_ptr->buffer, (fc_is_leaf) ? F_LEAF : 0);
			fc_ptr->page = BufferGetPage(fc_ptr->buffer);
			fc_ptr->block.blkno = BufferGetBlockNumber(fc_ptr->buffer);
			PredicateLockPageSplit(fc_rel,
								   BufferGetBlockNumber(fc_buffer),
								   BufferGetBlockNumber(fc_ptr->buffer));
		}

		/*
		 * 现在我们知道新页面应该去哪个块，设置向下链接元组指向它们。
		 */
		for (fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
		{
			ItemPointerSetBlockNumber(&(fc_ptr->itup->t_tid), fc_ptr->block.blkno);
			GistTupleSetValid(fc_ptr->itup);
		}

		/*
		 * 如果这是一个根分割，我们直接在这里构造新根页面的向下链接，而不是要求调用者插入它们。将新根页面与子页面一起添加到列表中。
		 */
		if (fc_is_rootsplit)
		{
			IndexTuple *fc_downlinks;
			int			fc_ndownlinks = 0;
			int			fc_i;

			fc_rootpg.buffer = fc_buffer;
			fc_rootpg.page = PageGetTempPageCopySpecial(BufferGetPage(fc_rootpg.buffer));
			GistPageGetOpaque(fc_rootpg.page)->flags = 0;

			/* 准备所有向下链接的向量 */
			for (fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
				fc_ndownlinks++;
			fc_downlinks = palloc(sizeof(IndexTuple) * fc_ndownlinks);
			for (fc_i = 0, fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
				fc_downlinks[fc_i++] = fc_ptr->itup;

			fc_rootpg.block.blkno = GIST_ROOT_BLKNO;
			fc_rootpg.block.num = fc_ndownlinks;
			fc_rootpg.list = gistfillitupvec(fc_downlinks, fc_ndownlinks,
										  &(fc_rootpg.lenlist));
			fc_rootpg.itup = NULL;

			fc_rootpg.next = fc_dist;
			fc_dist = &fc_rootpg;
		}
		else
		{
			/* 准备返回给调用者的分割信息 */
			for (fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
			{
				GISTPageSplitInfo *fc_si = palloc(sizeof(GISTPageSplitInfo));

				fc_si->buf = fc_ptr->buffer;
				fc_si->downlink = fc_ptr->itup;
				*fc_splitinfo = lappend(*fc_splitinfo, fc_si);
			}
		}

		/*
		 * 填充所有页面。所有页面都是新的，即新分配的空页面，或旧页面的临时副本。
		 */
		for (fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
		{
			char	   *fc_data = (char *) (fc_ptr->list);

			for (fc_i = 0; fc_i < fc_ptr->block.num; fc_i++)
			{
				IndexTuple	fc_thistup = (IndexTuple) fc_data;

				if (PageAddItem(fc_ptr->page, (Item) fc_data, IndexTupleSize(fc_thistup), fc_i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
					elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(fc_rel));

				/*
				 * 如果这是第一个插入/更新的元组，让调用者知道它落在了哪个页面上。
				 */
				if (fc_newblkno && ItemPointerEquals(&fc_thistup->t_tid, &(*fc_itup)->t_tid))
					*fc_newblkno = fc_ptr->block.blkno;

				fc_data += IndexTupleSize(fc_thistup);
			}

			/* 设置右链接 */
			if (fc_ptr->next && fc_ptr->block.blkno != GIST_ROOT_BLKNO)
				GistPageGetOpaque(fc_ptr->page)->rightlink =
					fc_ptr->next->block.blkno;
			else
				GistPageGetOpaque(fc_ptr->page)->rightlink = fc_oldrlink;

			/*
			 * 标记除了最右侧页面之外的所有页面，使用 follow-right
			 * 标志。它将在下行链路插入到父节点后被清除，但这确保了如果我们在那之前出错，索引仍然是一致的。（在缓冲构建模式下，任何错误都会中止索引构建，因此这不是必要的。）
			 */
			if (fc_ptr->next && !fc_is_rootsplit && fc_markfollowright)
				GistMarkFollowRight(fc_ptr->page);
			else
				GistClearFollowRight(fc_ptr->page);

			/*
			 * 将原始页面的 NSN 复制到所有页面。F_FOLLOW_RIGHT 标志确保扫描将在下行链路插入之前跟随右链接。
			 */
			GistPageSetNSN(fc_ptr->page, fc_oldnsn);
		}

		/*
		 * gistXLogSplit() 需要 WAL 记录大量页面，为此准备 WAL 插入。注意：此处指定的页面和数据段的数量必须与 gistXLogSplit() 中的计算匹配！
		 */
		if (!fc_is_build && RelationNeedsWAL(fc_rel))
			XLogEnsureRecordSpace(fc_npage, 1 + fc_npage * 2);

		START_CRIT_SECTION();

		/*
		 * 必须在 XLogInsert 之前标记缓冲区为脏，即使我们仍将在下面更改它们的不透明字段。
		 */
		for (fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
			MarkBufferDirty(fc_ptr->buffer);
		if (BufferIsValid(fc_leftchildbuf))
			MarkBufferDirty(fc_leftchildbuf);

		/*
		 * 链中的第一页是一个临时的工作副本，旨在替换旧页面。将其复制到旧页面上。
		 */
		PageRestoreTempPage(fc_dist->page, BufferGetPage(fc_dist->buffer));
		fc_dist->page = BufferGetPage(fc_dist->buffer);

		/*
		 * 写入 WAL 记录。
		 *
		 * 然而，如果我们正在构建新的索引，我们还不 WAL 记录更改。父子之间的 LSN-NSN 互锁要求 LSN 永远不能向后移动，因此将 LSN 设置为一个小于任何可能生成的真实或虚假未记录 LSN 的值。（在索引构建期间不能有并发扫描，因此我们暂时不需要能够检测并发分裂。）
		 */
		if (fc_is_build)
			fc_recptr = GistBuildLSN;
		else
		{
			if (RelationNeedsWAL(fc_rel))
				fc_recptr = gistXLogSplit(fc_is_leaf,
									   fc_dist, fc_oldrlink, fc_oldnsn, fc_leftchildbuf,
									   fc_markfollowright);
			else
				fc_recptr = gistGetFakeLSN(fc_rel);
		}

		for (fc_ptr = fc_dist; fc_ptr; fc_ptr = fc_ptr->next)
			PageSetLSN(fc_ptr->page, fc_recptr);

		/*
		 * 将新的子缓冲区返回给调用者。
		 *
		 * 如果这是根分裂，我们已经以新根页面的形式插入了下行指针。因此，我们可以释放所有新的缓冲区，并仅保持根页面被锁定。
		 */
		if (fc_is_rootsplit)
		{
			for (fc_ptr = fc_dist->next; fc_ptr; fc_ptr = fc_ptr->next)
				UnlockReleaseBuffer(fc_ptr->buffer);
		}
	}
	else
	{
		/*
		 * 空间足够。如果 ntup==0，我们总是会到这里。
		 */
		START_CRIT_SECTION();

		/*
		 * 删除旧元组（如果有），然后插入新元组（如果有）。如果可能，使用 PageIndexTupleOverwrite 的快速路径。
		 */
		if (OffsetNumberIsValid(fc_oldoffnum))
		{
			if (fc_ntup == 1)
			{
				/* 一对一替换，因此使用 PageIndexTupleOverwrite */
				if (!PageIndexTupleOverwrite(fc_page, fc_oldoffnum, (Item) *fc_itup,
											 IndexTupleSize(*fc_itup)))
					elog(ERROR, "failed to add item to index page in \"%s\"",
						 RelationGetRelationName(fc_rel));
			}
			else
			{
				/* 删除旧元组，然后将新元组附加到页面 */
				PageIndexTupleDelete(fc_page, fc_oldoffnum);
				gistfillbuffer(fc_page, fc_itup, fc_ntup, InvalidOffsetNumber);
			}
		}
		else
		{
			/* 仅将新元组附加到页面末尾 */
			gistfillbuffer(fc_page, fc_itup, fc_ntup, InvalidOffsetNumber);
		}

		MarkBufferDirty(fc_buffer);

		if (BufferIsValid(fc_leftchildbuf))
			MarkBufferDirty(fc_leftchildbuf);

		if (fc_is_build)
			fc_recptr = GistBuildLSN;
		else
		{
			if (RelationNeedsWAL(fc_rel))
			{
				OffsetNumber fc_ndeloffs = 0,
							fc_deloffs[1];

				if (OffsetNumberIsValid(fc_oldoffnum))
				{
					fc_deloffs[0] = fc_oldoffnum;
					fc_ndeloffs = 1;
				}

				fc_recptr = gistXLogUpdate(fc_buffer,
										fc_deloffs, fc_ndeloffs, fc_itup, fc_ntup,
										fc_leftchildbuf);
			}
			else
				fc_recptr = gistGetFakeLSN(fc_rel);
		}
		PageSetLSN(fc_page, fc_recptr);

		if (fc_newblkno)
			*fc_newblkno = fc_blkno;
	}

	/*
	 * 如果我们为子页面插入了下行链接，则设置 NSN 并清除左子页面上的 F_FOLLOW_RIGHT 标志，以便并发扫描知道仅在查看父页面后才跟随右链接。
	 *
	 * 请注意，我们是在写入 WAL 记录 *之后* 执行此操作。这意味着 WAL 记录中的可能完整页面图像不包括这些更改，即使页面是从完整页面图像恢复的，这些更改也必须被重放。这是一个鸡和蛋的问题：如果我们先更新子页面，我们将不知道即将写入的 WAL 记录的 recptr。
	 */
	if (BufferIsValid(fc_leftchildbuf))
	{
		Page		fc_leftpg = BufferGetPage(fc_leftchildbuf);

		GistPageSetNSN(fc_leftpg, fc_recptr);
		GistClearFollowRight(fc_leftpg);

		PageSetLSN(fc_leftpg, fc_recptr);
	}

	END_CRIT_SECTION();

	return fc_is_split;
}

/*
 * 进行插入到GiST索引的工作例程。请注意
 * 这个例程假设它是在一个短暂的内存上下文中调用的，
 * 所以它不麻烦释放palloc分配的空间。
 */
void gistdoinsert(Relation fc_r, IndexTuple fc_itup, Size fc_freespace,
			 GISTSTATE *fc_giststate, Relation fc_heapRel, bool fc_is_build)
{
	ItemId		fc_iid;
	IndexTuple	fc_idxtuple;
	GISTInsertStack fc_firststack;
	GISTInsertStack *fc_stack;
	GISTInsertState fc_state;
	bool		fc_xlocked = false;

	memset(&fc_state, 0, sizeof(GISTInsertState));
	fc_state.freespace = fc_freespace;
	fc_state.r = fc_r;
	fc_state.heapRel = fc_heapRel;
	fc_state.is_build = fc_is_build;

	/* 从根节点开始 */
	fc_firststack.blkno = GIST_ROOT_BLKNO;
	fc_firststack.lsn = 0;
	fc_firststack.retry_from_parent = false;
	fc_firststack.parent = NULL;
	fc_firststack.downlinkoffnum = InvalidOffsetNumber;
	fc_state.stack = fc_stack = &fc_firststack;

	/*
	 * 沿着最小罚款路径向下走，同时更新父指针
	 * 使用我们正在插入的键。如果我们在中间崩溃，
	 * 树是一致的，尽管可能的父更新是浪费的。
	 */
	for (;;)
	{
		/*
		 * 如果在树下降时我们拆分了内部页面，我们必须
		 * 在父节点重试。(通常，下面的LSN-NSN互锁也会
		 * 捕获到这一点并导致我们重试。但是在索引构建过程中
		 * LSN不会被更新。)
		 */
		while (fc_stack->retry_from_parent)
		{
			if (fc_xlocked)
				LockBuffer(fc_stack->buffer, GIST_UNLOCK);
			fc_xlocked = false;
			ReleaseBuffer(fc_stack->buffer);
			fc_state.stack = fc_stack = fc_stack->parent;
		}

		if (XLogRecPtrIsInvalid(fc_stack->lsn))
			fc_stack->buffer = ReadBuffer(fc_state.r, fc_stack->blkno);

		/*
		 * 保持乐观，首先获取共享锁。如果需要更新页面，
		 * 然后再交换为独占锁。
		 */
		if (!fc_xlocked)
		{
			LockBuffer(fc_stack->buffer, GIST_SHARE);
			gistcheckpage(fc_state.r, fc_stack->buffer);
		}

		fc_stack->page = (Page) BufferGetPage(fc_stack->buffer);
		fc_stack->lsn = fc_xlocked ?
			PageGetLSN(fc_stack->page) : BufferGetLSNAtomic(fc_stack->buffer);
		Assert(!RelationNeedsWAL(fc_state.r) || !XLogRecPtrIsInvalid(fc_stack->lsn));

		/*
		 * 如果这个页面被拆分，但由于插入的后端在此之前崩溃
		 * 而未将下链接插入到父节点，现在修复它。
		 */
		if (GistFollowRight(fc_stack->page))
		{
			if (!fc_xlocked)
			{
				LockBuffer(fc_stack->buffer, GIST_UNLOCK);
				LockBuffer(fc_stack->buffer, GIST_EXCLUSIVE);
				fc_xlocked = true;
				/* 在我们解锁时，可能有人已完成拆分 */
				if (!GistFollowRight(fc_stack->page))
					continue;
			}
			fc_gistfixsplit(&fc_state, fc_giststate);

			UnlockReleaseBuffer(fc_stack->buffer);
			fc_xlocked = false;
			fc_state.stack = fc_stack = fc_stack->parent;
			continue;
		}

		if ((fc_stack->blkno != GIST_ROOT_BLKNO &&
			 fc_stack->parent->lsn < GistPageGetNSN(fc_stack->page)) ||
			GistPageIsDeleted(fc_stack->page))
		{
			/*
			 * 检测到并发拆分或页面删除。无法保证此页面的下链接
			 * 与我们正在插入的元组一致，因此返回父节点并
			 * 重新选择最佳子节点。
			 */
			UnlockReleaseBuffer(fc_stack->buffer);
			fc_xlocked = false;
			fc_state.stack = fc_stack = fc_stack->parent;
			continue;
		}

		if (!GistPageIsLeaf(fc_stack->page))
		{
			/*
			 * 这是一个内部页面，因此继续向下遍历树。
			 * 查找具有最小插入罚款的子节点。
			 */
			BlockNumber fc_childblkno;
			IndexTuple	fc_newtup;
			GISTInsertStack *fc_item;
			OffsetNumber fc_downlinkoffnum;

			fc_downlinkoffnum = gistchoose(fc_state.r, fc_stack->page, fc_itup, fc_giststate);
			fc_iid = PageGetItemId(fc_stack->page, fc_downlinkoffnum);
			fc_idxtuple = (IndexTuple) PageGetItem(fc_stack->page, fc_iid);
			fc_childblkno = ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid));

			/*
			 * 检查它是否不是来自9.1之前的剩余无效元组
			 */
			if (GistTupleIsInvalid(fc_idxtuple))
				ereport(ERROR,
						(errmsg("index \"%s\" contains an inner tuple marked as invalid",
								RelationGetRelationName(fc_r)),
						 errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
						 errhint("Please REINDEX it.")));

			/*
			 * 检查表示目标子节点的键是否与
			 * 我们正在插入的键一致。如果不一致，更新它。
			 */
			fc_newtup = gistgetadjusted(fc_state.r, fc_idxtuple, fc_itup, fc_giststate);
			if (fc_newtup)
			{
				/*
				 * 将共享锁交换为独占锁。注意，在我们解锁/锁定页面时，
				 * 页面可能会发生变化...
				 */
				if (!fc_xlocked)
				{
					LockBuffer(fc_stack->buffer, GIST_UNLOCK);
					LockBuffer(fc_stack->buffer, GIST_EXCLUSIVE);
					fc_xlocked = true;
					fc_stack->page = (Page) BufferGetPage(fc_stack->buffer);

					if (PageGetLSN(fc_stack->page) != fc_stack->lsn)
					{
						/* 在我们解锁时，页面已更改，重试 */
						continue;
					}
				}

				/*
				 * 更新元组。
				 *
				 * 在gistinserttuple()之后我们仍然保持锁定，
				 * 但它可能必须拆分页面以适应更新的元组。
				 * 在这种情况下，更新的元组可能迁移到拆分的另一半，
				 * 所以我们必须返回父节点并向下遍历到更适合新
				 * 元组的那一半。
				 */
				if (fc_gistinserttuple(&fc_state, fc_stack, fc_giststate, fc_newtup,
									fc_downlinkoffnum))
				{
					/*
					 * 如果这是一个根拆分，根页面继续作为
					 * 父节点，更新的元组进入了其中一个
					 * 子页面，因此我们只需从根页面重新尝试。
					 */
					if (fc_stack->blkno != GIST_ROOT_BLKNO)
					{
						UnlockReleaseBuffer(fc_stack->buffer);
						fc_xlocked = false;
						fc_state.stack = fc_stack = fc_stack->parent;
					}
					continue;
				}
			}
			LockBuffer(fc_stack->buffer, GIST_UNLOCK);
			fc_xlocked = false;

			/* 向下遍历到选定的子节点 */
			fc_item = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
			fc_item->blkno = fc_childblkno;
			fc_item->parent = fc_stack;
			fc_item->downlinkoffnum = fc_downlinkoffnum;
			fc_state.stack = fc_stack = fc_item;
		}
		else
		{
			/*
			 * 叶页面。插入新的键。我们已经在下降过程中更新了
			 * 所有父节点，但如果不适合，我们可能需要拆分该页面。
			 * gistinserttuple()将处理此问题。
			 */

			/*
			 * 将共享锁交换为独占锁。小心，在我们解锁/锁定页面时，
			 * 页面可能会发生变化...
			 */
			if (!fc_xlocked)
			{
				LockBuffer(fc_stack->buffer, GIST_UNLOCK);
				LockBuffer(fc_stack->buffer, GIST_EXCLUSIVE);
				fc_xlocked = true;
				fc_stack->page = (Page) BufferGetPage(fc_stack->buffer);
				fc_stack->lsn = PageGetLSN(fc_stack->page);

				if (fc_stack->blkno == GIST_ROOT_BLKNO)
				{
					/*
					 * 唯一可以变成内部页面而不是叶子页面的是
					 * 根页面，因此我们应该重新检查根页面
					 */
					if (!GistPageIsLeaf(fc_stack->page))
					{
						/*
						 * 非常罕见的情况：在解锁/锁定索引时，
						 * 页面数=1的情况增加了
						 */
						LockBuffer(fc_stack->buffer, GIST_UNLOCK);
						fc_xlocked = false;
						continue;
					}

					/*
					 * 我们不需要检查根拆分，因为检查
					 * 叶子/内部就足够识别根的拆分
					 */
				}
				else if ((GistFollowRight(fc_stack->page) ||
						  fc_stack->parent->lsn < GistPageGetNSN(fc_stack->page)) ||
						 GistPageIsDeleted(fc_stack->page))
				{
					/*
					 * 页面在我们暂时解锁页面时被拆分或删除。返回到父页面。
					 */
					UnlockReleaseBuffer(fc_stack->buffer);
					fc_xlocked = false;
					fc_state.stack = fc_stack = fc_stack->parent;
					continue;
				}
			}

			/* 现在 state.stack->(页面、缓冲区和块号) 指向叶子页面 */

			fc_gistinserttuple(&fc_state, fc_stack, fc_giststate, fc_itup,
							InvalidOffsetNumber);
			LockBuffer(fc_stack->buffer, GIST_UNLOCK);

			/* 在退出之前释放我们可能仍然持有的任何锁 */
			for (; fc_stack; fc_stack = fc_stack->parent)
				ReleaseBuffer(fc_stack->buffer);
			break;
		}
	}
}

/*
 * 遍历树找到从根页面到指定“子”块的路径。
 *
 * 返回一个新的插入栈，从“子”的父级开始，直到根。
 * *downlinkoffnum 设置为子块直接父级中的下行链接的偏移量。
 *
 * 为了防止死锁，这应该一次只锁定一个页面。
 */
static GISTInsertStack *
fc_gistFindPath(Relation fc_r, BlockNumber fc_child, OffsetNumber *fc_downlinkoffnum)
{
	Page		fc_page;
	Buffer		fc_buffer;
	OffsetNumber fc_i,
				fc_maxoff;
	ItemId		fc_iid;
	IndexTuple	fc_idxtuple;
	List	   *fc_fifo;
	GISTInsertStack *fc_top,
			   *fc_ptr;
	BlockNumber fc_blkno;

	fc_top = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
	fc_top->blkno = GIST_ROOT_BLKNO;
	fc_top->downlinkoffnum = InvalidOffsetNumber;

	fc_fifo = list_make1(fc_top);
	while (fc_fifo != NIL)
	{
		/* 获取下一个要访问的页面 */
		fc_top = linitial(fc_fifo);
		fc_fifo = list_delete_first(fc_fifo);

		fc_buffer = ReadBuffer(fc_r, fc_top->blkno);
		LockBuffer(fc_buffer, GIST_SHARE);
		gistcheckpage(fc_r, fc_buffer);
		fc_page = (Page) BufferGetPage(fc_buffer);

		if (GistPageIsLeaf(fc_page))
		{
			/*
			 * 因为我们从上到下扫描索引，队列中的所有其余页面
			 * 也必须是叶子页面。
			 */
			UnlockReleaseBuffer(fc_buffer);
			break;
		}

		/* 目前，内部页面从未被删除 */
		Assert(!GistPageIsDeleted(fc_page));

		fc_top->lsn = BufferGetLSNAtomic(fc_buffer);

		/*
		 * 如果 F_FOLLOW_RIGHT 被设置，右侧的页面没有
		 * 下行链接。这通常不应该发生..
		 */
		if (GistFollowRight(fc_page))
			elog(ERROR, "concurrent GiST page split was incomplete");

		if (fc_top->parent && fc_top->parent->lsn < GistPageGetNSN(fc_page) &&
			GistPageGetOpaque(fc_page)->rightlink != InvalidBlockNumber /* 计算前一个数据项的长度 */ )
		{
			/*
			 * 页面在我们查看其他地方时被拆分。我们在扫描父页面时没有看到
			 * 右侧页面的下行链接，所以现在将其添加到队列中。
			 *
			 * 将右侧页面放在队列前面，以便我们可以下一个访问它。
			 * 这很重要，因为如果这是最低的内部级别，刚好在叶子之上，
			 * 我们可能已经排队了一些叶子页面，并且我们假设
			 * 在叶子页面后面不会有任何非叶子页面。
			 */
			fc_ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
			fc_ptr->blkno = GistPageGetOpaque(fc_page)->rightlink;
			fc_ptr->downlinkoffnum = InvalidOffsetNumber;
			fc_ptr->parent = fc_top->parent;

			fc_fifo = lcons(fc_ptr, fc_fifo);
		}

		fc_maxoff = PageGetMaxOffsetNumber(fc_page);

		for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
		{
			fc_iid = PageGetItemId(fc_page, fc_i);
			fc_idxtuple = (IndexTuple) PageGetItem(fc_page, fc_iid);
			fc_blkno = ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid));
			if (fc_blkno == fc_child)
			{
				/* 找到了！ */
				UnlockReleaseBuffer(fc_buffer);
				*fc_downlinkoffnum = fc_i;
				return fc_top;
			}
			else
			{
				/* 将这个子项添加到稍后要访问的页面列表中 */
				fc_ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
				fc_ptr->blkno = fc_blkno;
				fc_ptr->downlinkoffnum = fc_i;
				fc_ptr->parent = fc_top;

				fc_fifo = lappend(fc_fifo, fc_ptr);
			}
		}

		UnlockReleaseBuffer(fc_buffer);
	}

	elog(ERROR, "failed to re-find parent of a page in index \"%s\", block %u",
		 RelationGetRelationName(fc_r), fc_child);
	return NULL;				/* 保持编译器安静 */
}

/*
 * 更新栈，以便 child->parent 是子项的正确父项。
 * 进入时必须独占锁定 child->parent，退出时也将保持锁定，
 * 但可能不再是同一页面。
 */
static void fc_gistFindCorrectParent(Relation fc_r, GISTInsertStack *fc_child, bool fc_is_build)
{
	GISTInsertStack *fc_parent = fc_child->parent;
	ItemId		fc_iid;
	IndexTuple	fc_idxtuple;
	OffsetNumber fc_maxoff;
	GISTInsertStack *fc_ptr;

	gistcheckpage(fc_r, fc_parent->buffer);
	fc_parent->page = (Page) BufferGetPage(fc_parent->buffer);
	fc_maxoff = PageGetMaxOffsetNumber(fc_parent->page);

	/* 检查下行链接是否仍在之前的位置 */
	if (fc_child->downlinkoffnum != InvalidOffsetNumber && fc_child->downlinkoffnum <= fc_maxoff)
	{
		fc_iid = PageGetItemId(fc_parent->page, fc_child->downlinkoffnum);
		fc_idxtuple = (IndexTuple) PageGetItem(fc_parent->page, fc_iid);
		if (ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid)) == fc_child->blkno)
			return;				/* 仍然在那里 */
	}

	/*
	 * 自从我们查看以来，页面已被更改。在正常操作期间，
	 * 每次页面更新都会改变其 LSN，因此我们记住的
	 * LSN 也应该发生变化。然而，在索引构建期间，
	 * 我们不会 WAL 日志记录更改，直到我们构建了索引，
	 * 因此 LSN 不会改变。在索引构建期间没有并发活动，
	 * 但我们可能已经自己更改了父页面。
	 */
	Assert(fc_parent->lsn != PageGetLSN(fc_parent->page) || fc_is_build);

	/*
	 * 扫描页面以重新找到下行链接。如果页面已被拆分，
	 * 它可能已移动到不同的页面，因此请按照右侧链接直到找到
	 * 它。
	 */
	while (true)
	{
		OffsetNumber fc_i;

		fc_maxoff = PageGetMaxOffsetNumber(fc_parent->page);
		for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
		{
			fc_iid = PageGetItemId(fc_parent->page, fc_i);
			fc_idxtuple = (IndexTuple) PageGetItem(fc_parent->page, fc_iid);
			if (ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid)) == fc_child->blkno)
			{
				/* 是的！！发现了 */
				fc_child->downlinkoffnum = fc_i;
				return;
			}
		}

		fc_parent->blkno = GistPageGetOpaque(fc_parent->page)->rightlink;
		fc_parent->downlinkoffnum = InvalidOffsetNumber;
		UnlockReleaseBuffer(fc_parent->buffer);
		if (fc_parent->blkno == InvalidBlockNumber)
		{
			/*
			 * 链的末端仍然没有找到父级。这是根页面拆分时非常非常
			 * 罕见的情况。
			 */
			break;
		}
		fc_parent->buffer = ReadBuffer(fc_r, fc_parent->blkno);
		LockBuffer(fc_parent->buffer, GIST_EXCLUSIVE);
		gistcheckpage(fc_r, fc_parent->buffer);
		fc_parent->page = (Page) BufferGetPage(fc_parent->buffer);
	}

	/*
	 * 糟糕!! 我们需要搜索树来找到父节点...，但在此之前我们应该
	 * 释放所有旧的父节点
	 */

	fc_ptr = fc_child->parent->parent;	/* child->parent 已经在上面释放 */
	while (fc_ptr)
	{
		ReleaseBuffer(fc_ptr->buffer);
		fc_ptr = fc_ptr->parent;
	}

	/* 好的，找到新路径 */
	fc_ptr = fc_parent = fc_gistFindPath(fc_r, fc_child->blkno, &fc_child->downlinkoffnum);

	/* 按照调用者的预期读取所有缓冲区 */
	/* 注意我们在这里不锁定它们或进行 gistcheckpage! */
	while (fc_ptr)
	{
		fc_ptr->buffer = ReadBuffer(fc_r, fc_ptr->blkno);
		fc_ptr->page = (Page) BufferGetPage(fc_ptr->buffer);
		fc_ptr = fc_ptr->parent;
	}

	/* 将新的父链安装到堆栈中 */
	fc_child->parent = fc_parent;

	/* 递归调用正常处理 */
	LockBuffer(fc_child->parent->buffer, GIST_EXCLUSIVE);
	fc_gistFindCorrectParent(fc_r, fc_child, fc_is_build);
}

/*
 * 为 'buf' 中的页面形成一个下链接指针。
 */
static IndexTuple fc_gistformdownlink(Relation fc_rel, Buffer fc_buf, GISTSTATE *fc_giststate,
				 GISTInsertStack *fc_stack, bool fc_is_build)
{
	Page		fc_page = BufferGetPage(fc_buf);
	OffsetNumber fc_maxoff;
	OffsetNumber fc_offset;
	IndexTuple	fc_downlink = NULL;

	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	for (fc_offset = FirstOffsetNumber; fc_offset <= fc_maxoff; fc_offset = OffsetNumberNext(fc_offset))
	{
		IndexTuple	fc_ituple = (IndexTuple)
		PageGetItem(fc_page, PageGetItemId(fc_page, fc_offset));

		if (fc_downlink == NULL)
			fc_downlink = CopyIndexTuple(fc_ituple);
		else
		{
			IndexTuple	fc_newdownlink;

			fc_newdownlink = gistgetadjusted(fc_rel, fc_downlink, fc_ituple,
										  fc_giststate);
			if (fc_newdownlink)
				fc_downlink = fc_newdownlink;
		}
	}

	/*
	 * 如果页面完全为空，我们无法为其形成有意义的下链接。
	 * 但是我们必须为该页面插入一个下链接。只要与父页面的下链接一致，
	 * 任何键都可以，这样我们就可以合法地将其插入到父节点中。
	 * 最小的下链接，匹配尽可能少的扫描，会是最好的，以防止扫描做无用功，
	 * 但我们不知道如何构造它。所以我们只使用被拆分的原始页面的下链接——
	 * 这距离最优解已经尽可能远了，但这样也可以。
	 */
	if (!fc_downlink)
	{
		ItemId		fc_iid;

		LockBuffer(fc_stack->parent->buffer, GIST_EXCLUSIVE);
		fc_gistFindCorrectParent(fc_rel, fc_stack, fc_is_build);
		fc_iid = PageGetItemId(fc_stack->parent->page, fc_stack->downlinkoffnum);
		fc_downlink = (IndexTuple) PageGetItem(fc_stack->parent->page, fc_iid);
		fc_downlink = CopyIndexTuple(fc_downlink);
		LockBuffer(fc_stack->parent->buffer, GIST_UNLOCK);
	}

	ItemPointerSetBlockNumber(&(fc_downlink->t_tid), BufferGetBlockNumber(fc_buf));
	GistTupleSetValid(fc_downlink);

	return fc_downlink;
}


/*
 * 完成 state->stack->page 的不完整拆分。
 */
static void fc_gistfixsplit(GISTInsertState *fc_state, GISTSTATE *fc_giststate)
{
	GISTInsertStack *fc_stack = fc_state->stack;
	Buffer		fc_buf;
	Page		fc_page;
	List	   *fc_splitinfo = NIL;

	ereport(LOG,
			(errmsg("fixing incomplete split in index \"%s\", block %u",
					RelationGetRelationName(fc_state->r), fc_stack->blkno)));

	Assert(GistFollowRight(fc_stack->page));
	Assert(OffsetNumberIsValid(fc_stack->downlinkoffnum));

	fc_buf = fc_stack->buffer;

	/*
	 * 读取拆分页面链，跟随右链接。为每个页面构造一个下链接元组。
	 */
	for (;;)
	{
		GISTPageSplitInfo *fc_si = palloc(sizeof(GISTPageSplitInfo));
		IndexTuple	fc_downlink;

		fc_page = BufferGetPage(fc_buf);

		/* 形成要插入到父节点的新下链接元组 */
		fc_downlink = fc_gistformdownlink(fc_state->r, fc_buf, fc_giststate, fc_stack, fc_state->is_build);

		fc_si->buf = fc_buf;
		fc_si->downlink = fc_downlink;

		fc_splitinfo = lappend(fc_splitinfo, fc_si);

		if (GistFollowRight(fc_page))
		{
			/* 锁定下一个页面 */
			fc_buf = ReadBuffer(fc_state->r, GistPageGetOpaque(fc_page)->rightlink);
			LockBuffer(fc_buf, GIST_EXCLUSIVE);
		}
		else
			break;
	}

	/* 插入下链接 */
	fc_gistfinishsplit(fc_state, fc_stack, fc_giststate, fc_splitinfo, false);
}

/*
 * 在 stack->buffer 中插入或替换一个元组。如果 'oldoffnum' 有效，
 * 则替换 'oldoffnum' 处的元组，否则将该元组作为新元组插入。
 * 'stack' 表示从根到被更新页面的路径。
 *
 * 调用者必须对 stack->buffer 持有独占锁。锁在返回时仍然保持，但如果
 * 页面被拆分，则页面可能不包含插入的元组。若页面被拆分，函数返回 true，
 * 否则返回 false。
 */
static bool fc_gistinserttuple(GISTInsertState *fc_state, GISTInsertStack *fc_stack,
				GISTSTATE *fc_giststate, IndexTuple fc_tuple, OffsetNumber fc_oldoffnum)
{
	return fc_gistinserttuples(fc_state, fc_stack, fc_giststate, &fc_tuple, 1, fc_oldoffnum,
							InvalidBuffer, InvalidBuffer, false, false);
}

/* ----------------
 * gistinserttuple() 的扩展工作马版本。此版本允许
 * 插入多个元组，或用多个元组替换单个元组。
 * 这用于在页面拆分时递归更新父级中的下链接。
 *
 * 如果 leftchild 和 rightchild 是有效的，我们正在插入/替换
 * rightchild 的下链接，并且 leftchild 是它的左兄弟。我们清除
 * F_FOLLOW_RIGHT 标志，并在插入下链接的原子操作中更新 leftchild 的 NSN。
 *
 * 为了避免长时间占用锁，当递归向上更新父项时，锁定机制在这里有点特殊。进入时，
 * 调用者必须对 stack->buffer 持有独占锁，如果给定，还需对 leftchild 和 rightchild 持锁。返回时：
 *
 *	- 当 'unlockbuf' 为真时，释放对 stack->buffer 的锁。页面
 *	  始终保持固定不动。
 *	- 当 'unlockleftchild' 为真时，释放对 'leftchild' 的锁。页面
 *	  保持固定不动。
 *	- 'rightchild' 的锁和固定操作始终被释放。
 *
 * 如果页面需要拆分，返回 'true'。请注意，如果页面被拆分，
 * 插入/更新的元组可能被插入到 stack->buffer 的右兄弟而不是 stack->buffer 本身。
 */
static bool fc_gistinserttuples(GISTInsertState *fc_state, GISTInsertStack *fc_stack,
				 GISTSTATE *fc_giststate,
				 IndexTuple *fc_tuples, int fc_ntup, OffsetNumber fc_oldoffnum,
				 Buffer fc_leftchild, Buffer fc_rightchild,
				 bool fc_unlockbuf, bool fc_unlockleftchild)
{
	List	   *fc_splitinfo;
	bool		fc_is_split;

	/*
	 * 在我们打算修改页面之前，检查任何读写冲突（在可序列化隔离级别）
	 */
	CheckForSerializableConflictIn(fc_state->r, NULL, BufferGetBlockNumber(fc_stack->buffer));

	/* 将元组插入到页面，必要时拆分页面 */
	fc_is_split = gistplacetopage(fc_state->r, fc_state->freespace, fc_giststate,
							   fc_stack->buffer,
							   fc_tuples, fc_ntup,
							   fc_oldoffnum, NULL,
							   fc_leftchild,
							   &fc_splitinfo,
							   true,
							   fc_state->heapRel,
							   fc_state->is_build);

	/*
	 * 在递归向上之前，如果页面被拆分，释放对子页面的锁定。我们在更新
	 * 父级时不需要保持它们被锁定。
	 */
	if (BufferIsValid(fc_rightchild))
		UnlockReleaseBuffer(fc_rightchild);
	if (BufferIsValid(fc_leftchild) && fc_unlockleftchild)
		LockBuffer(fc_leftchild, GIST_UNLOCK);

	/*
	 * 如果我们必须拆分，则在父页中插入/更新下链接。如果调用者要求我们释放
	 * 对 stack->buffer 的锁，则告诉 gistfinishsplit() 在安全时尽早执行此操作。
	 * 如果我们不需要拆分，则由我们自己释放。
	 */
	if (fc_splitinfo)
		fc_gistfinishsplit(fc_state, fc_stack, fc_giststate, fc_splitinfo, fc_unlockbuf);
	else if (fc_unlockbuf)
		LockBuffer(fc_stack->buffer, GIST_UNLOCK);

	return fc_is_split;
}

/*
 * 通过在父页面中插入/更新下链接，完成一个不完整的拆分。'splitinfo' 包含所有
 * 参与拆分的子页面，按从左到右的顺序。
 *
 * 进入时，调用者必须持有对 stack->buffer 和 'splitinfo' 中所有子页面的锁定。
 * 如果 'unlockbuf' 为真，则在返回时会释放对 stack->buffer 的锁。子页面始终保持解锁和未固定。
 */
static void fc_gistfinishsplit(GISTInsertState *fc_state, GISTInsertStack *fc_stack,
				GISTSTATE *fc_giststate, List *fc_splitinfo, bool fc_unlockbuf)
{
	GISTPageSplitInfo *fc_right;
	GISTPageSplitInfo *fc_left;
	IndexTuple	fc_tuples[2];

	/* 拆分总是至少包含两个部分 */
	Assert(list_length(fc_splitinfo) >= 2);

	/*
	 * 我们需要为每个新页面插入下链接，并更新拆分中原始（最左侧）页面的下链接。
	 * 从最右侧页面开始，一次插入一个下链接，直到只剩下两个页面。
	 * 最后，插入最后一个新页面的下链接，并将原始页面的下链接作为一个操作更新。
	 */
	LockBuffer(fc_stack->parent->buffer, GIST_EXCLUSIVE);

	/*
	 * 从右到左插入兄弟节点的下链接，直到只剩下两个兄弟节点。
	 */
	for (int fc_pos = list_length(fc_splitinfo) - 1; fc_pos > 1; fc_pos--)
	{
		fc_right = (GISTPageSplitInfo *) list_nth(fc_splitinfo, fc_pos);
		fc_left = (GISTPageSplitInfo *) list_nth(fc_splitinfo, fc_pos - 1);

		fc_gistFindCorrectParent(fc_state->r, fc_stack, fc_state->is_build);
		if (fc_gistinserttuples(fc_state, fc_stack->parent, fc_giststate,
							 &fc_right->downlink, 1,
							 InvalidOffsetNumber,
							 fc_left->buf, fc_right->buf, false, false))
		{
			/*
			 * 如果父页面被拆分，现有的下链接可能已移动。
			 */
			fc_stack->downlinkoffnum = InvalidOffsetNumber;
		}
		/* gistinserttuples() 解锁了 right->buf. */
	}

	fc_right = (GISTPageSplitInfo *) lsecond(fc_splitinfo);
	fc_left = (GISTPageSplitInfo *) linitial(fc_splitinfo);

	/*
	 * 最后插入剩余右页的下连接，并更新
	 * 原始页的下连接以不包含已移动到新页的元组。
	 */
	fc_tuples[0] = fc_left->downlink;
	fc_tuples[1] = fc_right->downlink;
	fc_gistFindCorrectParent(fc_state->r, fc_stack, fc_state->is_build);
	(void) fc_gistinserttuples(fc_state, fc_stack->parent, fc_giststate,
							fc_tuples, 2,
							fc_stack->downlinkoffnum,
							fc_left->buf, fc_right->buf,
							true,	/* 解锁父节点 */
							fc_unlockbuf	/* 如果调用者希望，则解锁 stack->buffer */
		);

	/*
	 * 当我们更新下连接时，下连接可能已移动。即使页面
	 * 没有分裂，由于 gistinserttuples() 实现通过移除和重新插入
	 * 来更新旧元组！
	 */
	fc_stack->downlinkoffnum = InvalidOffsetNumber;

	Assert(fc_left->buf == fc_stack->buffer);

	/*
	 * 如果我们在插入新元组时为了调整内部页的下连接而拆分了
	 * 页面，那么这个页面可能不再是新元组的正确页面。到此
	 * 页的下连接可能无法涵盖新元组，它可能需要去新的右
	 * 兄弟页。告诉调用者往回走一遍栈，在父级检查插入页。
	 *
	 * 通常，在树下降过程中，LSN-NSN的互锁会检测到并发的
	 * 拆分（由我们自己），并导致我们在父级重试。但在索引
	 * 构建期间，该机制无效，因为我们在索引构建期间不进行
	 * WAL 记录，也不更新 LSN。
	 */
	fc_stack->retry_from_parent = true;
}

/*
 * gistSplit -- 拆分树中的页并填充用于 XLOG 和真实写入
 * 缓冲区的结构。该函数是递归的，即它将拆分页，直到键
 * 可以适合每个页。
 */
SplitedPageLayout *
gistSplit(Relation fc_r,
		  Page fc_page,
		  IndexTuple *fc_itup,		/* 包含压缩条目 */
		  int fc_len,
		  GISTSTATE *fc_giststate)
{
	IndexTuple *fc_lvectup,
			   *fc_rvectup;
	GistSplitVector fc_v;
	int			fc_i;
	SplitedPageLayout *fc_res = NULL;

	/* 这不应该递归得太深，但小心总是好的 */
	check_stack_depth();

	/* 拆分空页是没有意义的 */
	Assert(fc_len > 0);

	/*
	 * 如果单个元组无法适应一页，那么无论如何拆分都没有帮助。
	 */
	if (fc_len == 1)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
						IndexTupleSize(fc_itup[0]), GiSTPageSize,
						RelationGetRelationName(fc_r))));

	memset(fc_v.spl_lisnull, true,
		   sizeof(bool) * fc_giststate->nonLeafTupdesc->natts);
	memset(fc_v.spl_risnull, true,
		   sizeof(bool) * fc_giststate->nonLeafTupdesc->natts);
	gistSplitByKey(fc_r, fc_page, fc_itup, fc_len, fc_giststate, &fc_v, 0);

	/* 形成左向量和右向量 */
	fc_lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (fc_len + 1));
	fc_rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (fc_len + 1));

	for (fc_i = 0; fc_i < fc_v.splitVector.spl_nleft; fc_i++)
		fc_lvectup[fc_i] = fc_itup[fc_v.splitVector.spl_left[fc_i] - 1];

	for (fc_i = 0; fc_i < fc_v.splitVector.spl_nright; fc_i++)
		fc_rvectup[fc_i] = fc_itup[fc_v.splitVector.spl_right[fc_i] - 1];

	/* 完成拆分（可能需要另一次拆分） */
	if (!gistfitpage(fc_rvectup, fc_v.splitVector.spl_nright))
	{
		fc_res = gistSplit(fc_r, fc_page, fc_rvectup, fc_v.splitVector.spl_nright, fc_giststate);
	}
	else
	{
		ROTATEDIST(fc_res);
		fc_res->block.num = fc_v.splitVector.spl_nright;
		fc_res->list = gistfillitupvec(fc_rvectup, fc_v.splitVector.spl_nright, &(fc_res->lenlist));
		fc_res->itup = gistFormTuple(fc_giststate, fc_r, fc_v.spl_rattr, fc_v.spl_risnull, false);
	}

	if (!gistfitpage(fc_lvectup, fc_v.splitVector.spl_nleft))
	{
		SplitedPageLayout *fc_resptr,
				   *fc_subres;

		fc_resptr = fc_subres = gistSplit(fc_r, fc_page, fc_lvectup, fc_v.splitVector.spl_nleft, fc_giststate);

		/* 安装在列表的尾部 */
		while (fc_resptr->next)
			fc_resptr = fc_resptr->next;

		fc_resptr->next = fc_res;
		fc_res = fc_subres;
	}
	else
	{
		ROTATEDIST(fc_res);
		fc_res->block.num = fc_v.splitVector.spl_nleft;
		fc_res->list = gistfillitupvec(fc_lvectup, fc_v.splitVector.spl_nleft, &(fc_res->lenlist));
		fc_res->itup = gistFormTuple(fc_giststate, fc_r, fc_v.spl_lattr, fc_v.spl_lisnull, false);
	}

	return fc_res;
}

/*
 * 创建一个 GISTSTATE 并填充关于索引的信息
 */
GISTSTATE *
initGISTstate(Relation fc_index)
{
	GISTSTATE  *fc_giststate;
	MemoryContext fc_scanCxt;
	MemoryContext fc_oldCxt;
	int			fc_i;

	/* 安全检查以保护 GISTSTATE 中的固定大小数组 */
	if (fc_index->rd_att->natts > INDEX_MAX_KEYS)
		elog(ERROR, "numberOfAttributes %d > %d",
			 fc_index->rd_att->natts, INDEX_MAX_KEYS);

	/* 创建将持有 GISTSTATE 的内存上下文 */
	fc_scanCxt = AllocSetContextCreate(CurrentMemoryContext,
									"GiST scan context",
									ALLOCSET_DEFAULT_SIZES);
	fc_oldCxt = MemoryContextSwitchTo(fc_scanCxt);

	/* 创建并填充 GISTSTATE */
	fc_giststate = (GISTSTATE *) palloc(sizeof(GISTSTATE));

	fc_giststate->scanCxt = fc_scanCxt;
	fc_giststate->tempCxt = fc_scanCxt;	/* 调用者如有需要必须进行更改 */
	fc_giststate->leafTupdesc = fc_index->rd_att;

	/*
	 * 截断的 tupdesc 用于非叶子索引元组，不包含
	 * INCLUDE 属性。
	 *
	 * 它用于在元组调整和页拆分期间形成元组。
	 * B-tree 为每个截断元组创建简化的元组描述符，
	 * 因为它执行此操作的频率较低：在页拆分期间不用
	 * 形成截断元组。此外，B-tree 不像 GiST 那样在
	 * 内部页上调整元组。
	 */
	fc_giststate->nonLeafTupdesc = CreateTupleDescCopyConstr(fc_index->rd_att);
	fc_giststate->nonLeafTupdesc->natts =
		IndexRelationGetNumberOfKeyAttributes(fc_index);

	for (fc_i = 0; fc_i < IndexRelationGetNumberOfKeyAttributes(fc_index); fc_i++)
	{
		fmgr_info_copy(&(fc_giststate->consistentFn[fc_i]),
					   index_getprocinfo(fc_index, fc_i + 1, GIST_CONSISTENT_PROC),
					   fc_scanCxt);
		fmgr_info_copy(&(fc_giststate->unionFn[fc_i]),
					   index_getprocinfo(fc_index, fc_i + 1, GIST_UNION_PROC),
					   fc_scanCxt);

		/* 操作类不要求提供压缩方法 */
		if (OidIsValid(index_getprocid(fc_index, fc_i + 1, GIST_COMPRESS_PROC)))
			fmgr_info_copy(&(fc_giststate->compressFn[fc_i]),
						   index_getprocinfo(fc_index, fc_i + 1, GIST_COMPRESS_PROC),
						   fc_scanCxt);
		else
			fc_giststate->compressFn[fc_i].fn_oid = InvalidOid;

		/* 操作类不要求提供解压缩方法 */
		if (OidIsValid(index_getprocid(fc_index, fc_i + 1, GIST_DECOMPRESS_PROC)))
			fmgr_info_copy(&(fc_giststate->decompressFn[fc_i]),
						   index_getprocinfo(fc_index, fc_i + 1, GIST_DECOMPRESS_PROC),
						   fc_scanCxt);
		else
			fc_giststate->decompressFn[fc_i].fn_oid = InvalidOid;

		fmgr_info_copy(&(fc_giststate->penaltyFn[fc_i]),
					   index_getprocinfo(fc_index, fc_i + 1, GIST_PENALTY_PROC),
					   fc_scanCxt);
		fmgr_info_copy(&(fc_giststate->picksplitFn[fc_i]),
					   index_getprocinfo(fc_index, fc_i + 1, GIST_PICKSPLIT_PROC),
					   fc_scanCxt);
		fmgr_info_copy(&(fc_giststate->equalFn[fc_i]),
					   index_getprocinfo(fc_index, fc_i + 1, GIST_EQUAL_PROC),
					   fc_scanCxt);

		/* 操作类不要求提供距离方法 */
		if (OidIsValid(index_getprocid(fc_index, fc_i + 1, GIST_DISTANCE_PROC)))
			fmgr_info_copy(&(fc_giststate->distanceFn[fc_i]),
						   index_getprocinfo(fc_index, fc_i + 1, GIST_DISTANCE_PROC),
						   fc_scanCxt);
		else
			fc_giststate->distanceFn[fc_i].fn_oid = InvalidOid;

		/* 操作类不要求提供获取方法 */
		if (OidIsValid(index_getprocid(fc_index, fc_i + 1, GIST_FETCH_PROC)))
			fmgr_info_copy(&(fc_giststate->fetchFn[fc_i]),
						   index_getprocinfo(fc_index, fc_i + 1, GIST_FETCH_PROC),
						   fc_scanCxt);
		else
			fc_giststate->fetchFn[fc_i].fn_oid = InvalidOid;

		/*
		 * 如果索引列具有指定的排序规则，在进行比较时应遵循该排序规则。
		 * 然而，对于非排序的索引数据类型，我们可能有一个可排序的存储类型。
		 * 如果没有索引排序规则，则指定默认排序规则，以防支持
		 * 函数需要排序规则。如果支持函数不关心排序规则，这样做是无害的，
		 * 所以我们就无条件地这样做。(我们可以选择调用 get_typcollation，
		 * 但那似乎是成本过高的做法---不会有任何情况下，GiST 存储类型
		 * 有非默认排序规则。)
		 */
		if (OidIsValid(fc_index->rd_indcollation[fc_i]))
			fc_giststate->supportCollation[fc_i] = fc_index->rd_indcollation[fc_i];
		else
			fc_giststate->supportCollation[fc_i] = DEFAULT_COLLATION_OID;
	}

	/* 没有 INCLUDE 属性的操作类信息 */
	for (; fc_i < fc_index->rd_att->natts; fc_i++)
	{
		fc_giststate->consistentFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->unionFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->compressFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->decompressFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->penaltyFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->picksplitFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->equalFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->distanceFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->fetchFn[fc_i].fn_oid = InvalidOid;
		fc_giststate->supportCollation[fc_i] = InvalidOid;
	}

	MemoryContextSwitchTo(fc_oldCxt);

	return fc_giststate;
}

void freeGISTstate(GISTSTATE *fc_giststate)
{
	/* 删除 scanCxt 即可 */
	MemoryContextDelete(fc_giststate->scanCxt);
}

/*
 * gistprunepage() -- 尝试从给定页面中删除 LP_DEAD 项。
 * 函数假定缓冲区是独占锁定的。
 */
static void fc_gistprunepage(Relation fc_rel, Page fc_page, Buffer fc_buffer, Relation fc_heapRel)
{
	OffsetNumber fc_deletable[MaxIndexTuplesPerPage];
	int			fc_ndeletable = 0;
	OffsetNumber fc_offnum,
				fc_maxoff;

	Assert(GistPageIsLeaf(fc_page));

	/*
	 * 遍历所有项目，查看哪些根据 LP_DEAD 标志需要删除。
	 */
	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	for (fc_offnum = FirstOffsetNumber;
		 fc_offnum <= fc_maxoff;
		 fc_offnum = OffsetNumberNext(fc_offnum))
	{
		ItemId		fc_itemId = PageGetItemId(fc_page, fc_offnum);

		if (ItemIdIsDead(fc_itemId))
			fc_deletable[fc_ndeletable++] = fc_offnum;
	}

	if (fc_ndeletable > 0)
	{
		TransactionId fc_latestRemovedXid = InvalidTransactionId;

		if (XLogStandbyInfoActive() && RelationNeedsWAL(fc_rel))
			fc_latestRemovedXid =
				index_compute_xid_horizon_for_tuples(fc_rel, fc_heapRel, fc_buffer,
													 fc_deletable, fc_ndeletable);

		START_CRIT_SECTION();

		PageIndexMultiDelete(fc_page, fc_deletable, fc_ndeletable);

		/*
		 * 将页面标记为不包含任何 LP_DEAD 项。这并不是
		 * 绝对正确（可能有一些最近被标记，但不在我们的目标项列表中），
		 * 但几乎总是正确的，而且检查它似乎不值得进行额外的页面扫描。
		 * 请记住，F_HAS_GARBAGE 反正只是一个提示。
		 */
		GistClearPageHasGarbage(fc_page);

		MarkBufferDirty(fc_buffer);

		/* XLOG 相关内容 */
		if (RelationNeedsWAL(fc_rel))
		{
			XLogRecPtr	fc_recptr;

			fc_recptr = gistXLogDelete(fc_buffer,
									fc_deletable, fc_ndeletable,
									fc_latestRemovedXid);

			PageSetLSN(fc_page, fc_recptr);
		}
		else
			PageSetLSN(fc_page, gistGetFakeLSN(fc_rel));

		END_CRIT_SECTION();
	}

	/*
	 * 注意：如果我们没有找到任何 LP_DEAD 项，则页面的
	 * F_HAS_GARBAGE 提示位被错误地设置了。然而，我们并不
	 * 努力花费单独的写入来清除它。我们将在拆分页面时清除它。
	 */
}
